// javamaps
// Copyright (c) 2010 Lup Gratian
//
// Bucket PR-Quadtree ce permite gasirea rapida a punctelor
// care se intersecteaza cu o anumita regiune.
package Rendering.Utils;
import Rendering.IVisual;
import java.util.*;
import Core.*;
import java.util.ArrayList;
import javax.rmi.CORBA.ValueHandlerMultiFormat;

public final class PointTree<T extends IVisual> {
    // Directiile copiilor unui nod.
    private static final int DIRECTION_NW = 0;
    private static final int DIRECTION_NE = 1;
    private static final int DIRECTION_SW = 2;
    private static final int DIRECTION_SE = 3;

    private static final double[] DirectionX = new double[] {
        -0.5, 0.5, -0.5, 0.5
    };
    private static final double[] DirectionY = new double[] {
        -0.5, -0.5, 0.5, 0.5
    };
    private static final double[] IntersectionX = new double[] {
        -1, 0, -1, 0
    };
    private static final double[] IntersectionY = new double[] {
        -1, -1, 0, 0
    };

    // Capacitatea maxima a unui nod frunza.
    private static int SPLIT_THRESHOLD = 8;

    public class NearestInfo {
        private T value_;
        private double distance_;

        // ------------------------------------------------
        public NearestInfo() {
            distance_ = Double.MAX_VALUE;
        }

        public NearestInfo(T value, double distance) {
            value_ = value;
            distance_ = distance;
        }

        // ------------------------------------------------
        public double X() { return value_.Position().X(); }
        public double Y() { return value_.Position().Y(); }

        public T Value() { return value_; }
        public void SetValue(T value) { value_ = value; }
        
        public double Distance() { return distance_; }
        public void SetDistance(double value) { distance_ = value; }
    }

    
    class Node {
        private Object[] children_;
        private ArrayList<T> points_;
        private double x_; // Centrul nodului.
        private double y_;
        private boolean leaf_;

        // ------------------------------------------------
        public Node(double x, double y, boolean leaf) {
            x_ = x;
            y_ = y;
            leaf_ = leaf;

            if(leaf) {
                points_ = new ArrayList<T>(SPLIT_THRESHOLD);
            }
            else {
                children_ = new Object[4];
            }
        }

        public Node(Point center, boolean leaf) {
            this(center.X(), center.Y(), leaf);
        }

        // ------------------------------------------------
        public Node Child(int direction) {
            assert((direction >= DIRECTION_NW) &&
                   (direction <= DIRECTION_SE));
            // ------------------------------------------------
            return (Node)children_[direction];
        }

        public void SetChild(Node child, int direction) {
            assert((direction >= DIRECTION_NW) &&
                   (direction <= DIRECTION_SE));
            // ------------------------------------------------
            children_[direction] = child;
        }

        public List<T> Points() { return points_; }
        public double X() { return x_; }
        public double Y() { return y_; }
        public boolean IsLeaf() { return leaf_; }

        public void MakeInternal() {
            assert(leaf_ == true);
            // ------------------------------------------------
            points_ = null;
            children_ = new Object[4];
            leaf_ = false;
        }

        public void MakeLeaf(ArrayList<T> list) {
            points_ = list;
            children_ = null;
            leaf_ = true;
        }

        // Pentru debugging.
        @Override
        public String toString() {
            // N, 10, 25 oXoX
            return (leaf_ ? "L:" + points_.size() + "; " : "N: ") + x_ + ", " + y_ + " " +
                   (leaf_ ? "" : (children_[0] != null ? "X" : "o") +
                                 (children_[1] != null ? "X" : "o") +
                                 (children_[2] != null ? "X" : "o") +
                                 (children_[3] != null ? "X" : "o"));
        }
    }

    /*
     * Membrii.
     */
    private Node root_;
    private int count_;
    private double width_;  // Latimea maxima a suprafetei.
    private double height_; // Inaltimea maxima a suprafetei.

    /*
     * Constructori.
     */
    public PointTree(double width, double height) {
        root_ = new Node(width / 2, height / 2, true);
        count_ = 0;
        width_ = width;
        height_ = height;
    }
    
    public PointTree(double width, double height,
                     Collection<T> values) {
        this(width, height);
        AddAll(values);
    }

    /*
     * Metode publice.
     */
    // Adauga un punct avand valoarea data. Daca punctul exista in arbore
    // acesta nu mai este adaugat, chiar daca valoare este diferita.
    public void Add(T value) {
        assert(value != null);
        // ------------------------------------------------
        // Determina locul de inserare.
        Point point = value.Position();
        double x = width_ / 2;
        double y = height_ / 2;
        double width = width_ / 2;
        double height = height_ / 2;
        
        Node node = root_;
        while(node.IsLeaf() == false) {
            int direction = Direction(point, node);
            x += width * DirectionX[direction];
            width /= 2;
            y += height * DirectionY[direction];
            height /= 2;

            node = node.Child(direction);
        }

        // Adauga punctul in nod. Daca se depaseste capacitatea
        // nodului se creeaza 4 copii in care se distribuie punctele.
        List<T> list = node.Points();
        list.add(value);
        count_++;

        if(list.size() > SPLIT_THRESHOLD) {
            // Nodul trebuie transformat intr-unul de tip intern.
            node.MakeInternal();
            
            for(int dir = DIRECTION_NW; dir <= DIRECTION_SE; dir++) {
                double childX = x + (width * DirectionX[dir]);
                double childY = y + (height * DirectionY[dir]);
                Node child = new Node(childX, childY, true /* leaf */);
                node.SetChild(child, dir); // Leaga de parinte.

                // Insereaza punctele care se intersecteaza cu nodul copil.
                int count = list.size();
                for(int i = 0; i < count; i++) {
                    T temp = list.get(i);
                    if(PointInRegion(temp.Position(), childX, childY, width, height)) {
                        child.Points().add(temp);
                    }
                }
            }
        }
    }

    // Adauga toate punctele specificate.
    public void AddAll(Collection<T> values) {
        assert(values != null);
        // ------------------------------------------------
        Iterator<T> valuesIt = values.iterator();
        while(valuesIt.hasNext()) {
            Add(valuesIt.next());
        }
    }

    // Sterge punctul specificat din arbore.
    public void Remove(T value) {
        assert(value != null);
        // ------------------------------------------------
        RemoveImpl(value, root_, width_ / 2, height_ / 2,
                                 width_ / 2, height_ / 2);
    }

    // Adauga in lista specificata toate punctele aflate in interiorul regiunii.
    public void Intersect(Region2D region, ObjectCollection<T> list) {
        assert(region != null);
        assert(list != null);
        // ------------------------------------------------
        if((root_ == null) || region.IsEmpty()) return;
        IntersectImpl(region, root_, width_ / 2, height_ / 2,
                                     width_ / 2, height_ / 2, list);
    }

    // Cauta punctul specificat si daca este gasit returneaza valoarea
    // asociata. Daca punctul nu este gasit se returneaza null.
    public T Find(T value) {
        assert(value != null);
        // ------------------------------------------------
        if(root_ == null) return null;
        return FindImpl(value, root_, width_ / 2, height_ / 2,
                                      width_ / 2, height_ / 2);
    }

    // Returneaza cel mai apropiat punct fata de cel specificat.
    public NearestInfo NearestPoint(Point point) {
        assert(point != null);
        // ------------------------------------------------
        if(root_ == null) return null;
        NearestInfo nearest = new NearestInfo();
        NearestPointImpl(point, root_, nearest, width_ / 2, height_ / 2,
                                                width_ / 2, height_ / 2);
        return nearest;
    }

    // Returneaza o lista cu toate punctele aflate la cel mult
    // 'maxDistance' fata de punctul specificat.
    public void Near(Point point, double maxDistance, ObjectCollection<T> list) {
        assert(point != null);
        assert(list != null);
        assert(maxDistance >= 0);
        // ------------------------------------------------
        if(root_ == null) return;
        NearestImpl(point, maxDistance, root_, list, width_ / 2, height_ / 2,
                                                     width_ / 2, height_ / 2);
    }

    public int Count() { return count_; }
    public double Width() { return width_; }
    public double Height() { return height_; }

    public void Clear() {
        root_ = new Node(width_ / 2, height_ / 2, true);
        count_ = 0;
    }

    /*
    * Metode private.
    */
    private boolean RemoveImpl(T value, Node node, double x, double y,
                               double width, double height) {
        if(node.IsLeaf()) {
            // Verifica daca punctul se afla in acest nod.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                if(points.get(i).equals(value)) {
                    points.remove(i); // Punctul a fost gasit!
                    count_--;
                    return true;
                }
            }
        }
        else {
            // Se cauta punctul in nodurile copil.
            for(int i = DIRECTION_NW; i <= DIRECTION_SE; i++) {
                double nextX = x + (width * DirectionX[i]);
                double nextY = y + (height * DirectionY[i]);

                if(PointInRegion(value.Position(), nextX, nextY, width, height)) {
                    // Punctul trebuie sa se gaseasca in aceast copil.
                    boolean status =  RemoveImpl(value, node.Child(i), nextX, nextY,
                                                 width / 2, height / 2);

                    // Verifica daca nodul poate fi compactat.
                    if(status && MergePossible(node)) {
                        ArrayList<T> list = new ArrayList<T>();
                        if(MergeNodes(node, list)) {
                             node.MakeLeaf(list);
                             // Se poate incerca inbinarea la un nivel superior.
                             return true;
                        }
                    }
                }
            }
        }

        return false; // Punctul nu a fost gasit.
    }

    private boolean MergePossible(Node node) {
         return node.Child(DIRECTION_NE).IsLeaf() ||
                node.Child(DIRECTION_NW).IsLeaf() ||
                node.Child(DIRECTION_SE).IsLeaf() ||
                node.Child(DIRECTION_SW).IsLeaf();
     }

    private boolean MergeNodes(Node node, List<T> list) {
        if(node.IsLeaf()) {
            // Copiaza punctele in lista.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                list.add(points.get(i));
            }

            return list.size() <= SPLIT_THRESHOLD;
        }
        else {
            for(int dir = DIRECTION_NW; dir <= DIRECTION_SE; dir++) {
                if(MergeNodes(node.Child(dir), list) == false) {
                    return false;
                }
            }

            return true;
        }
    }

    private void IntersectImpl(Region2D region, Node node, double x, double y,
                               double width, double height, ObjectCollection<T> list) {
        if(node.IsLeaf()) {
            // Verifica daca punctul se afla in acest nod.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                T point = points.get(i);
                if(region.Contains(point.Position()) && list.Valid(point)) {
                    list.Add(point);
                }
            }
        }
        else {
            // Verifica care dintre copii se intersecteaza cu regiunea
            // si apeleaza recursiv pentru fiecare.
            for(int i = DIRECTION_NW; i <= DIRECTION_SE; i++) {
                if(region.IntersectsWith(x + (IntersectionX[i] * width),
                                         y + (IntersectionY[i] * height),
                                         width, height)) {
                    // Regiunea se intersecteaza cu acest copil.
                    IntersectImpl(region, node.Child(i),
                                  x + (DirectionX[i] * width),
                                  y + (DirectionY[i] * height),
                                  width / 2, height / 2, list);
                }
            }
        }
    }

    private T FindImpl(T value, Node node, double x, double y,
                       double width, double height) {
        if(node.IsLeaf()) {
            // Verifica daca punctul se afla in acest nod.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                T point = points.get(i);
                if(point.equals(value)) {
                    return point;
                }
            }
        }
        else {
            // Verifica care dintre copii se intersecteaza cu regiunea
            // si apeleaza recursiv pentru fiecare.
            for(int i = DIRECTION_NW; i <= DIRECTION_SE; i++) {                
                double nextX = x + (width * DirectionX[i]);
                double nextY = y + (height * DirectionY[i]);

                if(PointInRegion(value.Position(), nextX, nextY, width, height)) {
                    // Este posibil ca punctul sa fie in aceasta regiune.
                    T result = FindImpl(value, node.Child(i), nextX, nextY,
                                       width / 2, height / 2);
                    if(result != null) return result;
                }
             }
        }

        return null; // Punctul nu a fost gasit.
    }

    private void NearestPointImpl(Point point, Node node, NearestInfo nearest,
                                  double x, double y, double width, double height) {
        if(node.IsLeaf()) {
            // Verifica toate punctele din acest nod.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                T temp = points.get(i);

                double distance = point.Distance(temp.Position());
                if(distance < nearest.Distance()) {
                    // Un punct mai apropiat a fost gasit.
                    nearest.SetDistance(distance);
                    nearest.SetValue(temp);
                }
            }
        }
        else {
            // Verifica care dintre copii se intersecteaza cu regiunea
            // si apeleaza recursiv pentru fiecare.
            for(int i = DIRECTION_NW; i <= DIRECTION_SE; i++) {
                if(node.Child(i) == null) continue;

                double nextX = x + (width  * DirectionX[i]);
                double nextY = y + (height * DirectionY[i]);

                if(Overlap(point, nearest.Distance(),
                           nextX, nextY, width, height)) {
                    // Este posibil ca in aceasta regiune sa fie un punct mai apropiat.
                    NearestPointImpl(point, node.Child(i), nearest,
                                     nextX, nextY, width / 2, height / 2);
                }
            }
        }
    }

    private void NearestImpl(Point point, double maxDistance, Node node,
                             ObjectCollection<T> list,
                             double x, double y, double width, double height) {
        if(node.IsLeaf()) {
            // Adauga toate punctele mai apropiate de 'maxDistance' unitati.
            List<T> points = node.Points();

            int count = points.size();
            for(int i = 0; i < count; i++) {
                T temp = points.get(i);

                double distance = point.Distance(temp.Position());
                if(distance < maxDistance) {
                    list.Add(temp);
                }
            }
        }
        else {
            // Verifica care dintre copii se intersecteaza cu regiunea
            // si apeleaza recursiv pentru fiecare.
            for(int i = DIRECTION_NW; i <= DIRECTION_SE; i++) {
                if(node.Child(i) == null) continue;

                double nextX = x + (width * DirectionX[i]);
                double nextY = y + (height * DirectionY[i]);

                if(Overlap(point, maxDistance,
                           nextX, nextY, width, height)) {
                    // Este posibil ca in aceasta regiune sa fie un punct mai apropiat.
                    NearestImpl(point, maxDistance, node.Child(i), list,
                                nextX, nextY, width / 2, height / 2);
                }
            }
        }
    }

    // Returneaza directia primului punct relativa la cel de-al doilea.
    private int Direction(double x, double y, double otherX, double otherY) {
        if(x < otherX) {
            if(y < otherY) {
                return DIRECTION_NW;
            }
            else return DIRECTION_SW;
        }
        else {
           if(y < otherY) {
               return DIRECTION_NE;
           }
           else return DIRECTION_SE;
       }
    }

    private int Direction(Point a, Node b) {
        return Direction(a.X(), a.Y(), b.X(), b.Y());
    }

    // Verifica daca un punct este in interiorul unei regiuni
    // centrate in coordonatele 'x' si 'y'.
    private boolean PointInRegion(Point point, double x, double y,
                                  double width, double height) {
        return (point.X() >= (x - (width / 2))) &&
               (point.Y() >= (y - (height / 2))) &&
               (point.X() <= (x + (width / 2))) &&
               (point.Y() <= (y + (height / 2)));
    }

    // Verifica daca cercul si dreptunghiul (centrat in x si y) se intersecteaza.
    private boolean Overlap(double circleX, double circleY, double radius,
                            double rectX, double rectY,
                            double rectWidth, double rectHeight) {
        double dx = circleX - rectX;
        double dy = circleY - rectY;

        // Cerc in afara dreptunghiului.
        if(dx > ((rectWidth / 2) + radius)) return false;
        if(dy > ((rectHeight / 2) + radius)) return false;

        // Cerc (partial) in interior.
        if(dx <= (rectWidth / 2)) return true;
        if(dy <= (rectHeight / 2)) return true;

        // Test intersectie cu coltul dreptunghiului
        // (se compara direct patratele pt. a nu mai folosi sqrt).
        double  distanceSq = (dx - (rectWidth / 2)) *
                             (dx - (rectWidth / 2)) +
                             (dy - (rectHeight / 2)) *
                             (dy - (rectHeight / 2));
        return distanceSq <= (radius * radius);
    }

     private boolean Overlap(Point circle, double radius,
                            double rectX, double rectY,
                            double rectWidth, double rectHeight) {
         return Overlap(circle.X(), circle.Y(), radius,
                        rectX, rectY, rectWidth, rectHeight);
     }
}